For example, a NAND-type flash memory or other such high-integration, high-capacity nonvolatile semiconductor memory is characterized by the fact that a portion of stored data becomes more susceptible to destruction (referred to as data error hereinafter) the more times rewriting is carried out. Normally, the percentage of data errors relative to all the stored data in a nonvolatile semiconductor memory is between 0.1 and 1.0%. This percentage increases as the number of rewrites increases.
In a case where a nonvolatile semiconductor memory like this is used, and, for example, configures a storage device such as a SSD (Solid State Drive), an ECC (Error Checking Correcting) processing part for checking and correcting a location where a data error has occurred is generally implemented as a dedicated hardware circuit in a memory controller inside the storage device.
The ECC process is divided into two processes: an ECC coding process for adding a parity code for error correction to user data to be recorded in a storage medium, and an ECC decoding process for using the added parity code to detect an error location when user data is read from the storage medium.
The ECC decoding process is divided into two processes: a parity checking process, and an error location computation process. The parity checking process computes a test value called a syndrome from the user data and the parity code, looks at this test value, and determines whether or not a data error exists. The error location computation process, in a case where it was determined that a data error exists in the parity checking process, further analyzes the test value and detects the location where the data error has occurred.
Generally speaking, the application of a cyclic code is often used in the ECC process. The most often used cyclic code is the BCH code (Bose Chaudhuri Hocquenghem Code).
When using a parity code generated by the BCH code, randomly generated bit errors in the user data can be corrected up to a preset maximum number (will be expressed as t). Adding a parity code with a length that is longer than t makes it possible to correct more errors. This t is called the number of error-correctable bits, and is a design parameter at the time the BCH code circuit is implemented.
Furthermore, a numerical computation in accordance with a Galois field GF(2m) with an element of 2m is used in the BCH code as a positive integer m. The Galois field is a closed finite set in which four arithmetic operations are defined. This m is also a design parameter at the time the BCH code circuit is implemented.
In a Galois field GF(2m) with an element of 2m, the total of the user data and parity code bit length is found to be less than 2m bits. The parity code bit length of the BCH code is stipulated as m×t using both of the design parameters. Consequently, the bit length k of the user data must satisfy:k<2m−m×t. 
Furthermore, addition (+) and subtraction (−) in a Galois field differ from ordinary arithmetic addition (ADD) and arithmetic subtraction (SUB) in which there is carrying and borrowing, and both of these operations become exclusive OR (XOR) for each bit. That is, there is no distinction made between addition and subtraction from the standpoint of a computation, and the result of adding/subtracting the same value is 0 (X+X=0, X−X=0).
Next, a method for generating a parity code from the BCH code will be described.
First, a user data polynomial U(x) is created. When the bit string of the user data is {uk-1, uk-2, . . . u1, u0}
the user polynomial U(x) is generated by respectively allocating each bit to the coefficient of a polynomial of degree (k−1), as shown below:U(x)=uk-1xk-1+uk-2xk-2+ . . . u1x+u0.
Next, a remainder polynomial R(x) is created.
The remainder polynomial R(x) is the following polynomial of degree (m×t−1), which is generated by dividing a value obtained by multiplying U(x) by xmt by a polynomial of degree (m×t), which is called a generator polynomial G(x):R(x)=rmt-1xmt-1+rmt-2xmt-2+ . . . r1x+r0.
The remainder polynomial is a parity polynomial, and each coefficient is a polynomial of either 1 or 0. Furthermore, each coefficient of the generator polynomial G(x) of the BCH code is either 1 or 0, and is uniquely stipulated in accordance with the design parameters m and t.
Lastly, these coefficients are returned to the bit string to produce the following bit string:
{rmt-1, rmt-2, . . . , r1, r0}.
This bit string becomes the parity code.
Next, a specific method for generating the parity code from the BCH code will be described.
For example, in a case where the design parameters are m=6 and t=2, the BCH code generator polynomial is uniquely stipulated as:G(x)x12+x10+x8+x5+x4+x3+1.
When it is supposed that all the user data values are 1, and that the length is 40 bits (k=40)
{11 . . . 111}
the user data polynomial becomes:U(x)=x36+x38+ . . . x2+x+1
The remainder obtained by dividing a value obtained by multiplying this by x12 by G(x) becomes:R(x)=x10+x9+x4+x3+1.
Consequently, the 12 bits
{011000011001}
obtained by returning the respective coefficients to the bit string become the parity code.
As the prior art of a circuit for realizing the generation of a parity code from the BCH code as described hereinabove, for example, there are Patent Literature 1 and Patent Literature 2.
Patent Literature 1 is such that a lookup table showing the corresponding relationships from the user data polynomial U(x) to the parity polynomial R(x) is stored beforehand in ROM (READ Only Memory), and parity code generation is carried out at high speed by referring to this table. Using the above-mentioned design parameters, the size of the table is k×(m×t).
Patent Literature 2 is a technique that takes advantage of the fact that the generator polynomial G(x) can be factorized in a minimal polynomial Mi(x) of t. For example, taking a case in which the above-mentioned G(x) is t=2 as an example, the G(x) can be factorized into two products, i.e., M1(x)=x6+x+1 and M3(x)=x6+x4+x2+x+1, but a computing unit is configured for carrying out division, which treats this minimal polynomial as a divisor, and multiplication for multiplying by xm, and finds the parity polynomial R(x) by inputting the U(x) into a pipeline circuit that concatenates these operations into t steps. In the Patent Literature 2, the maximum number of error-correctable bits can be freely selected from 1 up to t with one type of circuit.